package snippet;
import java.util.*;
public class 组合总和Ⅱ {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	int sum = 0;
	boolean use[] = new boolean[110];
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    	Arrays.sort(candidates);
    	backtracking(candidates,target,0);
    	System.out.println(result.size());
    	System.out.println(result);
    	return result;
    }
    
    public void backtracking(int[] candidates, int target, int index) {
    	if(sum > target) {
    		return;
    	}
    	if(sum == target) {
    		result.add(new ArrayList<>(item));
    	}
    	// 树层去重
    	for(int i = index; i < candidates.length; i++) {
    		// 当前值与前一个值相同 且前一个值未用，说明前一个值已经经过遍历并回溯了
    		// 前一个值与当前值相同，那么前一个值遍历过的组合会与当前值的一样，所以应跳过
			if(i > 0 && candidates[i-1] == candidates[i] && use[i-1] == false) {
				continue;
			}
			use[i] = true;
			item.add(candidates[i]);
    		sum += candidates[i];
    		backtracking(candidates, target, i + 1);
    		use[i] = false;
    		item.remove(item.size() - 1);
    		sum -= candidates[i];
		}
    }
    	
    public static void main(String[] args) {
    	int nums[] = {3,1,3,5,1,1};
		new 组合总和Ⅱ().combinationSum2(nums, 8);
	}
}
